package ebook.datastructure.typed.chapter7;

import Algorithms.classic.SortUtils;

/**
 * description: <br>
 * createTime: 2018/11/716:31 <br>
 *
 * @author zzh
 */
public class QuickSortRight {
    public static int[] quickSort(int[] array) {
        recQuickSort(array, 0, array.length - 1);
        return array;
    }


    private static void recQuickSort(int[] array, int left, int right) {
        if(right - left <= 0) {
            return;
        }
        int qivot = array[right];
        int mid = partitionIt(array, left, right, qivot);
        recQuickSort(array, left, mid - 1);
        recQuickSort(array, mid + 1, right);
    }

    public static int partitionIt(int[] array, int leftIndex, int rightIndex, int pivot) {
        int left = leftIndex - 1;
        int right = rightIndex;
        while(true) {
            while(array[++left] < pivot) {
                ;
            }
            while(right > 0 && array[--right] > pivot) {
                ;
            }
            if(left >= right) {
                break;
            }
            swap(array, left, right);
        }
        swap(array, left, rightIndex);
        return left;
    }


    public static void swap(int[] array, int leftIndex, int rightIndex) {
        int temp = array[leftIndex];
        array[leftIndex] = array[rightIndex];
        array[rightIndex] = temp;
    }

    public static void main(String[] args) {
        SortUtils.test(QuickSortRight::quickSort);
    }
}
